﻿namespace ProblemsSet
{
    public class Problem_106 : BaseProblem
    {
        public override object GetResult()
        {
            const int max = 12;
            
            long res = 0;
            for (var i = 2; i <= max/2; i++)
            {
                res += MathLogic.GetC(2*i, max)*GetK(i);
            }
            return res;
        }

        private static long GetK(long n)
        {
            if (n <= 2) return 1;
            long tmp = MathLogic.GetC(n, 2*n);
            tmp *= (n - 1);
            tmp /= 2*(n + 1);
            return tmp;
        }


        public override string Problem
        {
            get
            {
                return @"Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

S(B)  S(C); that is, sums of subsets cannot be equal.
If B contains more elements than C then S(B)  S(C).
For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4, only 1 of these pairs need to be tested for equality (first rule). Similarly, when n = 7, only 70 out of the 966 subset pairs need to be tested.

For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?

NOTE: This problem is related to problems 103 and 105.

";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 21384;
            }
        }

    }
}
